package com.sicheng.lc.周赛.分类.思维.数论;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/30 16:31
 */
public class 统计可以被K整除的下标对数目 {
    //https://leetcode.cn/problems/count-array-pairs-divisible-by-k/

    static int N = (int) 1e5;
    static ArrayList<Integer>[] list = new ArrayList[N + 1];
    int[] cnt = new int[N + 1];

    // 复杂度 O(NlogN)
    static {
        Arrays.setAll(list, k -> new ArrayList<>(150));
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j += i) {
                list[j].add(i); // i 是 j 的因子
            }
        }
    }

    public long countPairs(int[] nums, int k) {
        long res = 0;
        for (int j : nums) {
            int x = k / gcd(k, j);
            res += cnt[x];
            for (int v : list[j]) {
                cnt[v]++;
            }
        }
        return res;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        统计可以被K整除的下标对数目 s = new 统计可以被K整除的下标对数目();
        int[] nums = {1, 2, 3, 4};
        System.out.println(s.countPairs(nums, 5));
    }
}
